package com.mc.collection;

import lombok.*;

import java.util.HashMap;
import java.util.Objects;

/***
 * @ClassName BitMap
 * @Description todo
 * @Author CC
 * @Date: 2019/11/139:20
 * @Version 1.0
 */

@Setter
@Getter
@ToString
@AllArgsConstructor
@NoArgsConstructor
@EqualsAndHashCode
public class BitMap<K, V> {
    private Node<K, V>[] table;
    private static int size;
    private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    public void put(K k, V v) {
        //取key的hashcode
        int hash = Objects.hashCode(k);
        //计算槽位置 取模操作耗时:必须把将10进制转成2进制到内存中进行计算，然后再把结果转换成10进制
        //  位运算是直接在内存中进行，不需要经过这些转换
//        int i = hash % length;

        //初始化node数组
        if (table == null) {
            table = new Node[DEFAULT_INITIAL_CAPACITY];
        }
        int i = hash & (table.length - 1);
        if (table[i] == null) {
            table[i] = new Node<>(i, k, v, null);
        } else {
            //判断当前节点k是否和传入的k绝对相等(hash相等且==)
            Node<K, V> node = table[i];
            if ((node.hash == hash) && (node.k == k || (k != null && node.k.equals(k)))) {
                //替换当前node的value
                node.v = v;
            } else {
                for (; ; ) {
                    //如果遍历到尾部了,直接添加元素
                    if (node.next == null) {
                        node.next = new Node<>(hash, k, v, null);
                        break;
                    }
                    //判断节点next.key是否和当前k的值绝对相等
                    if ((node.next.hash == hash) && (node.next.k == k || (k != null && node.next.k.equals(k)))) {
                        node.next.v = v;
                        break;
                    }
                    //继续深度遍历
                    node = node.next;
                }
            }
        }
        size++;
        if (size >= table.length) {
            resize();
        }

    }

    private void resize() {
        int newCapacity = table.length << 1;
        Node<K, V>[] newTable = new Node[newCapacity];
        for (Node<K, V> oldNode : table) {
            if (oldNode == null) {
                continue;
            }
            for (; ; ) {
                Node<K, V> newNode;
                if (oldNode == null) {
                    break;
                }
                int i = oldNode.hash & (newTable.length - 1);
                if (newTable[i] == null) {
                    newNode = oldNode;
                    newNode.next = null;
                } else {
                    newNode = oldNode;
                    newNode.next = newTable[i];
                }
                newTable[i] = newNode;
                oldNode = newTable[i].next;
            }
        }
        table = newTable;


    }

    public V get(K k) {
        //获取hash
        int hash = Objects.hashCode(k);
//        int i = hash % table.length;
        int i = hash & (table.length - 1);
        if (table == null || table[i] == null) return null;
        Node<K, V> node = table[i];
        //判断key是否相等
        if ((node.hash == hash) && (node.k == k || k != null && node.k.equals(k))) {
            return node.v;
        }
        for (; ; ) {
            Node<K, V> nextNode = node.next;
            if (nextNode == null) {
                return null;
            }
            //判断key是否相等
            if ((nextNode.hash == hash) && (nextNode.k == k || k != null && nextNode.k.equals(k))) {
                return nextNode.v;
            }
            //深度遍历
            node = nextNode;

        }
    }

    @Setter
    @Getter
    @ToString
    @AllArgsConstructor
    @NoArgsConstructor
    @EqualsAndHashCode
    static class Node<K, V> {
        private int hash;
        private K k;
        private V v;
        private Node<K, V> next;

    }
}
